package com.demo.java.OD51_100.OD63;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【快递运输】问题-递归法
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145605565
 */
public class OdMain1 {
    /**
     * 使用递归方法来求解符合条件的最大子集数量。
     *
     * @param array    存储数值的数组
     * @param index    当前处理的数组索引
     * @param count    当前选择的元素个数
     * @param sum      当前选择元素的和
     * @param maxValue 允许的最大和
     * @return 最大的符合条件的子集数量
     */
    private static int solve(int[] array, int index, int count, int sum, int maxValue) {
        // 如果当前的和超出了最大值，或者已经遍历完整个数组，则返回
        if (sum > maxValue || index >= array.length) {
            return count - 1; // 返回选择的元素数 - 1 (避免选择了一个不合法的子集)
        }

        // 递归尝试选择当前元素 (result1)
        int result1 = solve(array, index + 1, count + 1, sum + array[index], maxValue);

        // 递归尝试跳过当前元素 (result2)
        int result2 = solve(array, index + 1, count, sum, maxValue);

        // 返回选择当前元素和不选择当前元素的最大结果
        return Math.max(result1, result2);
    }

    public static void main(String[] args) {
        try {
            // 创建扫描器对象来读取输入
            Scanner s = new Scanner(System.in);

            // 读取数组的输入，并按逗号分割
            String[] line = s.nextLine().split(",");

            // 读取最大和
            int maxValue = Integer.parseInt(s.nextLine());

            // 将字符串数组转换为整数数组
            int[] array = new int[line.length];
            for (int j = 0; j < line.length; ++j) {
                array[j] = Integer.parseInt(line[j]);
            }

            // 对数组进行排序 (确保递归过程中处理较小的元素时优先考虑)
            Arrays.sort(array);

            // 调用solve方法并输出结果
            System.out.println(solve(array, 0, 0, 0, maxValue));

        } catch (Exception e) {
            // 异常处理
            e.printStackTrace();
            System.out.println("input error");
        }
    }
}